package com.ljy.my_study.lintcode.K数之和;

import java.util.LinkedList;
import java.util.Queue;

/** 
* @author James
* @date 2018年9月30日 
*/
public class TestMain {
//	描述
//	给定 n 个不同的正整数，整数 k（k <= n）以及一个目标数字 target。　
//	在这 n 个数里面找出 k 个数，使得这 k 个数的和等于目标数字，求问有多少种方案？
//
//	您在真实的面试中是否遇到过这个题？  
//	样例
//	给出 [1,2,3,4]，k=2， target=5，[1,4] 和 [2,3] 是 2 个符合要求的方案，返回 2。
	public static void main(String[] args) {
//		int[] nums= {1,2,3,4,5};
//		int[] nums= {1,4,7,9,10,12,15,18,20,21,22,25,28,31,33,36,38,39,41,43,44,45,48,50,53};
//		System.out.println(kSum(nums,21,617));
		int[] nums= {1,3,4,5,6,8,11,14,16,19,20,23,25,28,30,33,34,36,39,41,43,45,46,48,51,53,55,56,58,59,60};
		System.out.println(kSum(nums,26,811));
	}
	
	public static int kSum(int[] A, int k, int target) {
		return list(A,target,k);
	}
	
	public static int list(int[] nums,int target,int k) {
		if(nums.length<k)return 0;
		int sum=0;
		Queue<Group> q=new LinkedList<>();
		if(k==1) {
			for(int i=0;i<nums.length;i++) {
				if(nums[i]==target) {
					sum++;
				}
			}
			return sum;
		}
		int count=1;
		while(count<nums.length) {
			q.offer(new Group(nums[count-1]));
			while(!q.isEmpty()) {
				sum+=list(q,nums,target,count,k);
				count++;
			}
		}
		return sum;
	}
	
	public static int list(Queue<Group> q,int[] nums,int target,int count,int k){
		int sum=0;
		Group g=q.poll();
		if(g.sum==target&&g.count==k) {
			return 1;
		}else if(g.sum>target||g.count>k) {
			return 0;
		}
		for(int i=count;i<nums.length;i++) {
			if(g.sum+nums[i]<=target&&g.count+1<=k) {
				Group newG=new Group(nums[i],g.sum,i,g.count);
				q.offer(newG);
				sum+=list(q,nums,target,i+1,k);
			}
		}
		return sum;
	}
	
	public static class Group {
		public int sum;
		public int count;
		
		public Group(int val) {
			this.sum=val;
			this.count++;
		}
		
		public Group(int val,int lastSum,int index,int lastCount){
			this.sum=lastSum+val;
			this.count=lastCount+1;
		}

		@Override
		public String toString() {
			return "{\"sum\":\"" + sum + "\",\"count\":\"" + count + "\"} ";
		}


	}
}
